/* 寻找中序线索二叉树的前驱结点 */

#include <iostream>
#include "InThreadBiTreefun.h"
using namespace std;

// 在中序线索二叉树中，找p的前驱结点
TNode *fun(TNode *T, TNode *p)
{
  // 如果该结点存在左孩子结点
  if (p->ltag==0){
    while(p->rtag==0)
      p=p->rchild;
    return p;
  }
  
  // 如果该结点没有左孩子结点
  else 
    return p->lchild;
}

int main()
{
  // 创建中序线索二叉树
  TNode *T = create_iTree();
  
  // 构建线索
  TNode *pre = NULL;
  if (T != NULL)
    {
      InTh(T, pre);
      pre->rchild = NULL;
      pre->rtag = 1;
    }

  // 随机一个结点
  TNode *p = T->rchild->lchild;
  
  // 找p结点的前驱结点
  cout << "pre is:" << fun(T, p)->data << endl;
  return 0;
}
